package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _148买卖股票的最佳时机III
 * @description
 * @date 2023/08/29 15:59
 * <p>
 * ******************************************************
 */
public class _148买卖股票的最佳时机III {


    public int maxProfit(int[] prices) {
        // dp[-1][...][0] = 0
        //解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
        //
        //dp[-1][...][1] = -infinity
        //解释：还没开始的时候，是不可能持有股票的。
        //因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
        //
        //dp[...][0][0] = 0
        //解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
        //
        //dp[...][0][1] = -infinity
        //解释：不允许交易的情况下，是不可能持有股票的。
        //因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
        // base case：
        //dp[-1][...][0] = dp[...][0][0] = 0
        //dp[-1][...][1] = dp[...][0][1] = -infinity
        //
        //状态转移方程：
        //dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
        //dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

        // 因为k=1;所以状态转移方程：
        // dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
        // dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
        // = max(dp[i-1][1][1], 0 - prices[i]) = max(dp[i-1][1][1], -prices[i])

        int n = prices.length;
        int[][][] dp = new int[n][3][2];

        for (int i = 0; i < n; i++) {
            for (int k = 2; k >= 1; k--) {
                if (i == 0) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][2][0];
    }
}
